package com.cuz.for2024;

public class T45 {
    public static void main(String[] args) {
        System.out.println(new T45().jump(new int[]{1,1,1,1}));
    }

    public int jump(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        if (nums[0] >= nums.length - 1) {
            return 1;
        }
        return jumpMin(nums, 0) + 1;
    }

    private int jumpMin(int[] nums, int i) {
        if (i == nums.length - 1) {
            return 0;
        }

        int far = nums[i];
        if (far + i >= nums.length - 1) {
            return 1;
        }
        int min = Integer.MAX_VALUE;
        for (int step = 1; step <= far; step++) {
            if (i + step >= nums.length) {
                continue;
            }
            min = Math.min(jumpMin(nums, i + step), min);
        }
        return min;
    }
}
